package com.yusong.algorithm;


import com.yusong.algorithm.data.DataConstants;

/**
 * 选择排序
 */
public class SelectSort extends AbstractSort {

    @Override
    public void sort(Comparable[] a) {
        int length = a.length;
        for (int i = 0; i < length; i++) {
            Comparable smallValue = a[i];
            int exchangeIndex = i;
            for (int j = i + 1; j < length; j++) {
                Comparable newValue = a[j];
                if (!less(smallValue, newValue)) {
                    exchangeIndex = j;
                    smallValue = newValue;
                }
            }
            exchange(a, i, exchangeIndex);
        }
    }

    public static void main(String[] args) {
        SelectSort selectSort = new SelectSort();
        selectSort.sort(DataConstants.NUM_SIMPLE);
        show(DataConstants.NUM_SIMPLE);
    }

}
/**
 * 选择排序说明
 * 算法：不断遍历找到最小的元素放到数组最前面
 * 时间复杂度 N*N/2
 * 运行时间与输入无关，已经遍历一遍的数据不会对下次遍历产生影响（即使是已经排序好的序列）
 * 其他算法更善于利用输入的初始状态
 */

